package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月17日
*时间：下午9:01:19
*/
public class Q73 {
    /**
     *@param preorder : A list of integers that preorder traversal of a tree
     *@param inorder : A list of integers that inorder traversal of a tree
     *@return : Root of a tree
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) {
            return null;
        }
        return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode buildTree(int[] preOrder, int[] inOrder, int startPreorder, int endPreorder, int startInorder, int endInorder) {

        if (startPreorder > endPreorder || startInorder > endInorder) {
            return null;
        }
        TreeNode root = new TreeNode(preOrder[startPreorder]);

        int divider = 0;
        while (divider <= endInorder && inOrder[divider] != root.val) {
            divider++;
        }

        int offSet = divider - startInorder - 1;
        root.left = buildTree(preOrder, inOrder, startPreorder + 1, startPreorder + 1 + offSet, startInorder, startInorder + offSet);
        root.right = buildTree(preOrder, inOrder, startPreorder + offSet + 2, endPreorder, divider + 1, endInorder);

        return root;
    }

    @Test
    public void testA() {
        int[] preorder = { 2, 1, 3 };
        int[] inorder = { 1, 2, 3 };
        TreeNode rs = buildTree(preorder, inorder);
        System.out.println(rs);
    }

}
